#ifndef BTL_ROBUSTESTIMATION_RANSAC
#define BTL_ROBUSTESTIMATION_RANSAC

#include <boost/optional.hpp>
#include <boost/random/random_number_generator.hpp>
#include <boost/random/mersenne_twister.hpp>
#include <vector>

namespace btl {
namespace robustestimation {

/// A ModelSearchSpace implements the model building and scoring functionality required for robust model selection.
///
/// To use one of the RANSAC-style RobustModelFinder classes you will have to implement ModelSearchSpace for your data.
///
/// Requirements:
/// - You need a type to represent a model of the data. For example, if you're fitting a 2D line to some data your model might be std::pair<double,double> representing a (slope, offset) pair.
/// - You need to know how many data points you have available.
/// - You need to be able to map from integer indexes in the range (0,N] to observations (this is easy if you have your data points in an array).
/// - You need to be able to calculate an error metric for a pair of (model, data point); error metrics should be additive
template <class ModelType>
class ModelSearchSpace
{
   public:
      /// @return The number of observations available to use for model fitting.
      virtual int numObservations() const = 0;

      /// Build a single model given a sample
      virtual ModelType buildModel(const int observations[], int numObservations) const {}

      /// Build any number of models given a sample.
      virtual void buildModels(const int observations[], int numObservations, std::vector<ModelType>& output) const;

      /// Score the given model against an observation.
      /// @note It is assumed that costs are additive.
      virtual double errorMetric(const ModelType& model, int observation) const = 0;
};

template <class ModelType, class RNG = boost::random_number_generator<boost::mt19937> >
class RobustModelFinder
{
   public:
      RobustModelFinder();
      virtual ~RobustModelFinder();

      virtual boost::optional<ModelType> findModel(const ModelSearchSpace<ModelType>& searchSpace, RNG& rng) = 0;
};

} //robustestimation
} //btl

namespace btl
{

using robustestimation::ModelSearchSpace;
using robustestimation::RobustModelFinder;

} //btl

// ====================================================================
// === Implementation

namespace btl {
namespace robustestimation {

template <class ModelType>
void ModelSearchSpace<ModelType>::buildModels(const int observations[], int numObservations, std::vector<ModelType>& output) const
{
   output.push_back(buildModel(observations, numObservations));
}

template <class ModelType, class RNG>
inline RobustModelFinder<ModelType,RNG>::RobustModelFinder() {}

template <class ModelType, class RNG>
inline RobustModelFinder<ModelType,RNG>::~RobustModelFinder() {}

} //robustestimation
} //btl

#endif //BTL_ROBUSTESTIMATION_RANSAC
